#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ERROR NULL

typedef int ElementType;
typedef struct PolyNode* PtrToLNode;
struct PolyNode 
{
    ElementType Data;
    PtrToLNode next;
};
typedef PtrToLNode Position; // Position指结点的内存地址
typedef PtrToLNode List;

int Length(List L)
{
    Position p = L;
    int cnt = 0;
    while (p)
    {
        cnt++;
        p = p->next;
    }
    return cnt;
}

Position FindKth(List L, int k)
{
    List p = L;
    int cnt = 1;
    while (p && cnt < k)
    {
        p = p->next;
        cnt++;
    }
        
    if (p && cnt == k)
        return p;
    return ERROR;
}

Position Find(List L, ElementType x)
{
    Position p = L;
    while (p && p->Data != x)
        p = p->next;
    if (p)
        return p;
    return ERROR;
}

List Insert(List L, ElementType x, int i)
{
    PtrToLNode p, prev; // p表示新结点，prev表示待插入结点的前驱结点
    // 因为如果是插入第1个位置，前驱结点prev是NULL，所以要特例处理
    if (i == 1)
    {
        p = (PtrToLNode) malloc(sizeof(struct PolyNode));
        p->Data = x;
        p->next = L;
        return p;
    }

    prev = FindKth(L, i - 1);
    if (!prev)
    {
        printf("插入位置错误\n");
        return ERROR;
    }
    p = (PtrToLNode) malloc(sizeof(struct PolyNode));
    p->Data = x;
    p->next = prev->next;
    prev->next = p;
    return L;
}

List Delete(List L, int i)
{
    PtrToLNode p, prev; // p表示待删除结点，prev表示待删除结点的前驱结点
    if (i == 1)
    {
        p = prev = L;
        prev = prev->next;
        free(p);
        return prev;
    }

    prev = FindKth(L, i - 1);
    if (!prev || !prev->next) // 待删除结点的前驱结点若为NULL或为线性表尾，都是不可以继续删除的
    {
        printf("删除位置错误\n");
        return ERROR;
    }
    p = prev->next;
    prev->next = p->next;
    free(p);
    return L;
}

int main()
{
    List L = NULL;
    for (int i = 1, j = 100; i <= 5 && j <= 500; i++, j += 100)
    {
        L = Insert(L, j, i);
    }

    L = Delete(L, 6);
    Position p;
    for (p = L; p != NULL; p = p->next)
        printf("%d\n", p->Data);

    // Position p;
    // // p = Find(L, 108);
    // // if (p)
    // //     printf("Found %d\n", p->Data);
    // // else
    // //     printf("Not found\n");
    // for (p = L; p; p = p->next)
    //     printf("%d\n", p->Data);
    return 0;
}